1697F - Too Many Constraints - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) (int((x).size()))
typedef vector<int> VI;
const int MX = 3e6;
int n;
VI adj[MX], _adj[MX];
int q[MX], qn;
int vis[MX], cn;

void DFS(int u) {
	int i, v;
	vis[u]++;
	for (i = sz(adj[u]) - 1; i >= 0; i--) {
		v = adj[u][i];
		if (!vis[v]) DFS(v);
	}
	q[qn++] = u;
}

void _DFS(int u) {
	int i, v;
	vis[u] = cn;
	for (i = sz(_adj[u]) - 1; i >= 0; i--) {
		v = _adj[u][i];
		if (!vis[v]) _DFS(v);
	}
}

void SCC() {
	int i, u, v;
	fill_n(vis, n, 0);
	qn = 0;
	for (u = 0; u < n; u++) {
		if (!vis[u]) DFS(u);
	}
	for (u = 0; u < n; u++) _adj[u].clear();
	for (u = 0; u < n; u++) {
		for (i = sz(adj[u]) - 1; i >= 0; i--) {
			v = adj[u][i];
			_adj[v].pb(u);
		}
	}
	fill_n(vis, n, 0);
	cn = 0;
	for (i = n - 1; i >= 0; i--) {
		u = q[i];
		if (!vis[u]) {
			cn++;
			_DFS(u);
		}
	}
}
#define NOT(x) ((x + N) % n)
#define con(x, y) adj[x].pb(y)
#define add_true(x) con(NOT(x), x)
#define add_false(x) con(x, NOT(x))
#define add_or(x, y) con(NOT(x), y), con(NOT(y), x)
#define add_imply(x, y) add_or(NOT(x), y)
#define add_same(x, y) add_or(x, NOT(y)), add_or(y, NOT(x))
#define add_diff(x, y) add_or(x, y), add_or(NOT(x), NOT(y))
#define add_must(x) add_or(x, x)
int N;
bool val[MX];

void init() {
	n = N * 2;
	for (int u = 0; u < n; u++) adj[u].clear();
}

bool SAT_2() {
	int i, j, u;
	SCC();
	for (u = 0; u < N; u++) {
		i = vis[u], j = vis[u + N];
		if (i == j) return 0;
		val[u] = (j < i), val[u + N] = (i < j);
	}
	return 1;
}

struct constraint{
    int tp, i, j, x;
};

void solve() {
    int nn, m, k;
    cin >> nn >> m >> k;
    int kk = k + 2;
    N = nn * kk;
    init();
    vector<constraint>c(m);
    for (int i = 0; i < m; i++) {
        cin >> c[i].tp >> c[i].i;
        if (c[i].tp != 1) cin >> c[i].j;
        --c[i].i, --c[i].j;
        cin >> c[i].x;
    }
    for (int i = 0; i < nn; i++) {
        for (int j = 0; j < kk - 1; j++) 
            add_imply(i * kk + j + 1, i * kk + j);
        add_must(i * kk + 1);
        add_must(NOT(i * kk + k + 1));
    }
    for (int i = 0; i < nn - 1; i++) for (int j = 0; j < kk; j++)
        add_imply(i * kk + j, (i + 1) * kk + j);
    for (int i = 0; i < m; i++) {
        if (c[i].tp == 1) 
            add_or(c[i].i * kk + c[i].x + 1, NOT(c[i].i * kk + c[i].x));
        else if (c[i].tp == 2) {
            for (int a = max(1, c[i].x - k); a <= min(k, c[i].x - 1); a++) {
                add_imply(c[i].i * kk + a, NOT(c[i].j * kk + (c[i].x - a) + 1));
                add_imply(c[i].j * kk + a, NOT(c[i].i * kk + (c[i].x - a) + 1));
            }
        }
        else {
            for (int a = max(1, c[i].x - k); a <= min(k, c[i].x - 1); a++) {
                add_imply(NOT(c[i].i * kk + a + 1), c[i].j * kk + (c[i].x - a));
                add_imply(NOT(c[i].j * kk + a + 1), c[i].i * kk + (c[i].x - a));
            }
        }
    }
    bool flag = SAT_2();
    if (!flag) {cout << -1 << endl;}
    else {
        int rst = 0;
        for (int i = 0; i < nn; i++) {
            for (int j = 0; j < kk; j++) if (val[i * kk + j]) rst = j;
            cout << rst << ' ';
        }
        cout << endl;
    }
                
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int tc = 1;
    cin >> tc;
    while (tc--) solve();
    return 0;
}